/*
 * @lc app=leetcode.cn id=785 lang=java
 *
 * [785] 判断二分图
 */

// @lc code=start
class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] visited = new int[graph.length];
        for(int i = 0; i < graph.length; i++) {
            if(visited[i] == 0 && !dfs(graph, i, 1, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int v, int color, int[] visited) {
        if(visited[v] != 0) {
            return visited[v] == color;
        }

        visited[v] = color;
        for(int next : graph[v]) {
            if(!dfs(graph, next, -color, visited)) {
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

